package leetcode._0118;

import java.util.ArrayList;
import java.util.List;

/**
 * Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
 *
 *
 * In Pascal's triangle, each number is the sum of the two numbers directly above it.
 *
 * Example:
 *
 * Input: 5
 * Output:
 * [
 *      [1],
 *     [1,1],
 *    [1,2,1],
 *   [1,3,3,1],
 *  [1,4,6,4,1]
 * ]
 */

/**
 * https://leetcode.com/problems/pascals-triangle/
 */
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> temp = new ArrayList<List<Integer>>();
        if (numRows == 0) {
            return temp;
        }
        firstRow(temp);
        for (int i = 1; i < numRows; i++) {
            temp.add(gerNextRow(temp.get(i - 1)));
        }
        return temp;
    }


    private void firstRow(List<List<Integer>> temp) {
        List<Integer> list = new ArrayList();
        list.add(1);
        temp.add(list);
    }

    public List<Integer> gerNextRow(List<Integer> pre) {
        List<Integer> nextRow = new ArrayList(pre.size() + 1);
        nextRow.add(1);
        for (int i = 1; i < pre.size(); i++) {
            nextRow.add(pre.get(i - 1) + pre.get(i));
        }
        nextRow.add(1);

        return nextRow;
    }
}